Vertices, Edges, & Degree (Undirected)

A vertex's degree summarizes its local connectivity.

• The degree of a vertex $v$, written as $\deg(v)$, is the number of edges connected to it. A self-loop (an edge from $v$ to itself) adds 2 to the degree.
• An isolated vertex is a vertex with $\deg(v)=0$, meaning it has no connections. A leaf is a vertex with $\deg(v)=1$.
• The Handshaking Lemma states that the sum of degrees over all vertices is twice the number of edges: $\sum_v \deg(v) = 2|E|$. This is because each edge connects two vertices, contributing 1 to the degree of each.